\section{容器}
\subsection{vector}
vector类称作向量类，它实现了动态数组，用于元素数量变化的对象数组。像数组一样，vector类也用从0开始的下标表示元素的位置；但和数组不同的是，当vector对象创建后，数组的元素个数会随着vector对象元素个数的增大和缩小而自动变化。
\begin{itemize}
    \item \cppinline{vector()}：创建一个空的vector。
    \item \cppinline{void push_back(const T& x)}：向量尾部增加一个元素X。
    \item \cppinline{iterator insert(iterator it,const T& x)}：向量中迭代器指向元素前增加一个元素x。
    \item \cppinline{iterator insert(iterator it,int n,const T& x)}：向量中迭代器指向元素前增加n个相同的元素。
    \item  \cppinline{iterator insert(iterator it,const_iterator first,const_iterator last)}：向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据。
    \item  \cppinline{iterator erase(iterator it)}：删除向量中迭代器指向元素。
    \item  \cppinline{iterator erase(iterator first,iterator last)}：删除向量中[first,last)中元素。
    \item  \cppinline{void pop_back()}：删除向量中最后一个元素。
    \item  \cppinline{void clear()}：清空向量中所有元素。
    \item  \cppinline{reference at(int pos)}：返回pos位置元素的引用。
    \item  \cppinline{reference front()}：返回首元素的引用。
    \item  \cppinline{reference back()}：返回尾元素的引用。
    \item  \cppinline{iterator begin()}：返回向量头指针，指向第一个元素。
    \item  \cppinline{iterator end()}：返回向量尾指针，指向向量最后一个元素的下一个位置。
    \item  \cppinline{reverse_iterator rbegin()}：反向迭代器，指向最后一个元素。
    \item  \cppinline{reverse_iterator rend()}：反向迭代器，指向第一个元素之前的位置。
    \item  \cppinline{bool empty() const}：判断向量是否为空，若为空，则向量中无元素。
    \item  \cppinline{int size() const}：返回向量中元素的个数。
    \item  \cppinline{int capacity() const}：返回当前向量所能容纳的最大元素值。
    \item  \cppinline{int max_size() const}：返回最大可允许的vector元素数量值。
    \item  \cppinline{void swap(vector)}：交换两个同类型向量的数据。
    \item  \cppinline{void assign(int n,const T x)}：设置向量中第n个元素的值为x。
    \item  \cppinline{void assign(const_iterator first,const_iterator last)}：向量中[first,last)中元素设置成当前向量元素。
\end{itemize}
\subsubsection{vector成员函数}
\begin{enumerate}
    \item 构造和拷贝构造函数
          \begin{cpp}
              explicit vector ( const Allocator& = Allocator() );
              explicit vector ( size_type n, const T& value= T(), const Allocator& = Allocator() );
              template <class InputIterator>
              vector ( InputIterator first, InputIterator last, const Allocator& = Allocator() );
              vector ( const vector<T,Allocator>& x );
          \end{cpp}
          explicit:是防止隐式转换, Allocator是一种内存分配模式,一般是使用默认的。
          \begin{cpp}
              vector<int> A;  //创建一个空的的容器
              vector<int> B(10,100); //创建一个10个元素,每个元素值为100 vector
              vector<int> C(B.begin(),B.end()); //使用迭代器,可以取部分元素创建一个新的容器
              vector<int> D(C); //复制构造函数,创建一个和C一样的容器D
          \end{cpp}
    \item 重载了= 符号。
          \begin{cpp}
              vector<int> E; //生成vector E
              E = B;         //将容器B的元素复制给E
          \end{cpp}
    \item \cppinline{vector::operator[ ]}：重载了[ ]符号。
          \begin{cpp}
              reference  operator[] ( size_type n );
              const_reference  operator[] ( size_type n ) const;
          \end{cpp}
    \item \cppinline{vector::assign()}：将丢弃原来的元素用迭代器里面的内容替换(第一个函数是使用迭代器)，第二个函数是使用n个元素，每个元素的值为u替换容器中的内容。
          \begin{cpp}
              template <class InputIterator> void assign ( InputIterator first, InputIterator last );
              void assign ( size_type n, const T& u );
          \end{cpp}
    \item \cppinline{vector::at()}：下标访问元素。在函数的操作方面和下标访问元素一样，不同的是当这个函数越界时会抛出一个异常out\_of\_range。(V.at(0)：访问第一个下标元素。)
          \begin{cpp}
              const_reference at ( size_type n ) const;
              reference at ( size_type n );
          \end{cpp}
    \item vector::back()：同样，返回最后一个元素的值，注意与end()函数的区别。\\
          \begin{cpp}
              reference back ( );
              const_reference back ( ) const;
          \end{cpp}
    \item \cppinline{vector::begin()}：返回第一个元素的迭代器。
          \begin{cpp}
              iterator begin ();  //返回一个可变迭代器
              const_iterator begin () const; //返回一个常量的迭代器，不可变
          \end{cpp}
    \item \cppinline{vector::size_type capacity () const;}：返回vector的实际存储空间的大小，这个一般大于或等于vector元素个数，注意与size()函数的区别。
    \item \bashinline{vector::cbegin}：返回一个指向容器第一个元素的迭代器。
          \mint{cpp}{const_iterator cbegin() const noexcep}

    \item \cppinline{vector::cend}：返回一个指向容器最后一个元素后面元素的常量指针。
          \mint{cpp}{const_iterator cend() const noexcept}
    \item \cppinline{vector::clear()}：将容器里的内容清空，size值为0，但是存储空间没有改变。
    \item \cppinline{vector::crbegin()}：返回指向容器最后一个元素的常数指针。
          \mint{cpp}{const_reverse_iterator crbegin() const noexcept}
    \item \cppinline{vector::data}：返回一个直接指向vector内部创建的数组数据的指针。因为在vector中的元素被存储在一块连续的存储区，指针获取可以偏移访问数组中的任何元素。
          \begin{cpp}
              value_type* data() noexcept;
              const value_type* data() const noexcept;
          \end{cpp}
          \cppfile{code/STL/vec4/main.cpp}
    \item \cppinline{vector::emplace}：构造插入元素。通过在position插入一个新的元素扩展容器。新元素被使用args构造。这是高效增加容器大小的方法。position：在容器中新元素被替换的位置。args传到构造体的新元素。
          \begin{cpp}
              template <class... Args>
              iterator emplace (const_iterator position, Args&&... args);
          \end{cpp}
    \item \cppinline{vector::emplace_back}：插入一个新元素在vector的末尾。
          \begin{cpp}
              template <class... Args>
              void emplace_back (Args&&... args);
          \end{cpp}
    \item \cppinline{vector::empty()}：当元素个数为0时返回true，否则为false，根据的是元素个数而不是容器的存储空间的大小。
          \mint{cpp}{bool empty () const;}

    \item \cppinline{vector::end()}：返回最后一个元素的下一个位置的迭代器。
          \begin{cpp}
              iterator end ();
              const_iterator end () const;
          \end{cpp}
    \item \cppinline{vector::erase()}：删除元素或一段序列。返回迭代器指向删除元素后的位置。
          \begin{cpp}
              iterator erase ( iterator position );
              iterator erase ( iterator first, iterator last );
          \end{cpp}
    \item \cppinline{vector::front()}：返回第一个元素的值，与begin()函数有区别，begin()函数返回的是第一个元素的迭代器。
          \begin{cpp}
              reference front ( );
              const_reference front ( ) const;
          \end{cpp}
    \item \cppinline{vector::get_allocator}：返回一个allocator对象的拷贝。
          \mint{cpp}{allocator_type get_allocator() const noexcept;}
          \cppfile{code/STL/vec5/main.cpp}
    \item \cppinline{vector::insert()}：插入新的元素。\\
          \begin{cpp}
              iterator insert ( iterator position, const T& x );
              void insert ( iterator position, size_type n, const T& x );
              template <class InputIterator>
              void insert ( iterator position, InputIterator first, InputIterator last );
          \end{cpp}
          \begin{itemize}
              \item 第一个函数，在迭代器指定的位置前插入值为x的元素
              \item 第二个函数，在迭代器指定的位置前插入n个值为x的元素
              \item 第三个函数，在迭代器指定的位置前插入另外一个容器的一段序列迭代器first到last若插入新的元素后总得元素个数大于capacity，则重新分配空间
          \end{itemize}
    \item \cppinline{vector::max_size()}：返回容器的最大可以存储的元素个数，这是个极限，当容器扩展到这个最大值时就不能再自动增大。
          \mint{cpp}{size_type max_size () const;}
    \item \cppinline{vector::pop_back()}：删除最后一个元素。
    \item \cppinline{vector::push_back()}：在容器的最后一个位置插入元素x,如果size值大于capacity值，则将重新分配空间。\cppinline{void push_back ( const T& x );}
    \item \cppinline{vector::rbegin()}：反序的第一个元素，也就是正序最后一个元素。
          \begin{cpp}
              reverse_iterator rbegin();
              const_reverse_iterator rbegin() const;
          \end{cpp}
    \item \cppinline{vector::rend()}：反序的最后一个元素下一个位置，也相当于正序的第一个元素前一个位置。
          \begin{cpp}
              reverse_iterator rend();
              const_reverse_iterator rend() const;
          \end{cpp}
    \item \cppinline{vector::reserve()}：重新分配空间的大小，不过这个n值要比原来的capacity()返回的值大，不然存储空间保持不变，n值要比原来的实际存储空间大才能重新分配空间，但是最大值不可以大于max\_size的值，否则会抛出异常。函数原型：
          \mint{cpp}{void reserve ( size_type n );}
    \item \cppinline{vector::resize()}：重新分配容器的元素个数，这个还可以改容器的容量，如果重新分配的元素个数比原来的小，将截断序列，后面的部分丢弃，如果大于原来的个数，后面的值是c的值，默认为0。
          \mint{cpp}{void resize ( size_type sz, T c = T() );}
    \item \cppinline{vector::shrink_to_fit}：要求容器减小容量适应它的size。
          \mint{cpp}{void shrink_to_fit()}
          \cppfile{code/STL/vec6/main.cpp}
          \begin{bash}
              1.Capacity of myvec: 100
              2.Capacity of myvec: 100
              3.Capacity of myvec: 10
          \end{bash}
          \begin{cpp}
              // vector::shrink_to_fit
              #include <iostream>
              #include <vector>
              int main ()
              {
                      std::vector<int> myvector (100);
                      std::cout << "1. capacity of myvector: " << myvector.capacity() << '\n';

                      myvector.resize(10);
                      std::cout << "2. capacity of myvector: " << myvector.capacity() << '\n';
                      myvector.shrink_to_fit();
                      std::cout << "3. capacity of myvector: " << myvector.capacity() << '\n';
                      return 0;
                  }
          \end{cpp}
    \item \cppinline{vector::size()}: 返回容器中元素个数。函数原型：
          \mint{cpp}{size_type size() const;}
    \item \cppinline{vector::swap()}：交换这两个容器的内容，这涉及到存储空间的重新分配。
          \mint{cpp}{void swap ( vector<T,Allocator>& vec );}
\end{enumerate}
\subsection*{vector相关说明}
vector的元素不仅仅可以使int、double、string,还可以是结构体，但是要注意：结构体要定义为全局的，否则会出错。下面是一段简短的程序代码：
\cppfile{code/STL/vec1/main.cpp}
\textbf{算法}
使用reverse将元素翻转：需要头文件\cppinline{#include<algorithm>}。

\cppinline{reverse(vec.begin(),vec.end())}; 将元素翻转(在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含。使用sort排序需要头文件 \cppinline{#include<algorithm>}
\cppinline{sort(vec.begin(),vec.end());}(默认是按升序排列,即从小到大).可以通过重写排序比较函数按照降序比较，如下：
\begin{cpp}
    // 定义排序比较函数：
    bool Comp(const int &a,const int &b)
    {
            return a>b;
        }
\end{cpp}
调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。与其它容器不同，其内存空间只会增长，不会减小。先来看看"C++ Primer"中怎么说：为了支持快速的随机访问，vector容器的元素以连续方式存放，每一个元素都紧挨着前一个元素存储。设想一下，当vector添加一个元素时，为了满足连续存放这个特性，都需要重新分配空间、拷贝元素、撤销旧空间，这样性能难以接受。因此STL实现者在对vector进行内存分配时，其实际分配的容量要比当前所需的空间多一些。就是说，vector容器预留了一些额外的存储区，用于存放新添加的元素，这样就不必为每个新元素重新分配整个容器的内存空间。

关于vector的内存空间，有两个函数需要注意：size()成员指当前拥有的元素个数；capacity()成员指当前(容器必须分配新存储空间之前)可以存储的元素个数。reserve()成员可以用来控制容器的预留空间。vector另外一个特性在于它的内存空间会自增长，每当vector容器不得不分配新的存储空间时，会以加倍当前容量的分配策略实现重新分配。例如，当前capacity为50，当添加第51个元素时，预留空间不够用了，vector容器会重新分配大小为100的内存空间，作为新连续存储的位置。

\subsubsection*{vector内存释放}
由于vector的内存占用空间只增不减，比如你首先分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个。所有内存空间是在vector析构时候才能被系统回收。empty()用来检测容器是否为空的，clear()可以清空所有元素。但是即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收。如果需要空间动态缩小，可以考虑使用deque。如果非vector不可，可以用swap()来帮助你释放内存。具体方法如下：
\begin{cpp}
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(2);
    vector<int>().swap(nums);
\end{cpp}
或者如下：
\begin{cpp}
    {
        std::vector<int> tmp =   nums;
        nums.swap(tmp);
    }
\end{cpp}
swap()是交换函数，使vector离开其自身的作用域，从而强制释放vector所占的内存空间，总而言之，释放vector内存最简单的方法是vector<int>.swap(nums)。当时如果nums是一个类的成员，不能把vector<int>.swap(nums)写进类的析构函数中，否则会导致double free or corruption (fasttop)的错误，原因可能是重复释放内存。标准解决方法如下：
\begin{cpp}
    template < class T >
    void ClearVector( vector< T >& vt )
    {
            vector< T > vtTemp;
            veTemp.swap( vt );
        }
\end{cpp}
\subsubsection*{利用vector释放指针}
如果vector中存放的是指针，那么当vector销毁时，这些指针指向的对象不会被销毁，那么内存就不会被释放。如下面这种情况，vector中的元素时由new操作动态申请出来的对象指针：
\begin{cpp}
    #include <vector>
    using namespace std;
    vector<void *> v
\end{cpp}
每次new之后调用v.push\_back()该指针，在程序退出或者根据需要，用以下代码进行内存的释放：
\begin{cpp}
    for (vector<void *>::iterator it = v.begin(); it != v.end(); it ++)
    if (NULL != *it)
    {
            delete *it;
            *it = NULL;
        }
    v.clear();
\end{cpp}
vector是线性容器,它的元素严格的按照线性序列排序,和动态数组很相似,和数组一样,它的元素存储在一块连续的存储空间中,这也意味着我们不仅可以使用迭代器(iterator)访问元素,还可以使用指针的偏移方式访问,和常规数组不一样的是,vector能够自动存储元素,可以自动增长或缩小存储空间。vector的优点：
\begin{enumerate}
    \item 可以使用下标访问个别的元素
    \item 迭代器可以按照不同的方式遍历容器
    \item 可以在容器的末尾增加或删除元素
\end{enumerate}
和数组相比,虽然容器在自动处理容量的大小时会消耗更多的内存,但是容器能提供和数组一样的性能,而且能很好的调整存储空间大小和其它标准的顺序容器相比(deques or lists),能更有效访问容器内的元素和在末尾添加和删除元素,在其它位置添加和删除元素,vector则不及其它顺序容器,在迭代器和引用也不比lists支持的好容器的大小和容器的容量是有区别的,大小是指元素的个数,容量是分配的内存大小,容量一般等于或大于容器的大小,vector::size()返回容器的大小,vector::capacity()返回容量值,容量多于容器大小的部分用于以防容器的增加使用,每次重新分配内存都会很影响程序的性能,所以一般分配的容量大于容器的大小,若要自己指定分配的容量的大小,则可以使用vector::reserve(),但是规定的值要大于size()值。
\subsection{array}
\begin{itemize}
    \item \cppinline{array::at()}：返回一个在位置n上元素的引用。函数自动检查是否越界，如果越界则抛出out\_of\_range异常，[  ]获取元素则不会检查是否越界。（size\_type是unsign整型。）
          \begin{cpp}
              reference at ( size_type n);
              const_reference at ( size_type n  ) const;
          \end{cpp}
    \item \cppinline{array::back()}：返回array容器最后一个元素的引用。函数原型：
          \begin{cpp}
              reference back();
              const_reference back() const;
          \end{cpp}
    \item \cppinline{array::begin()}：返回指向array第一个元素的迭代器。函数原型：
          \begin{cpp}
              iterator begin() noexcept;
              const_iterator begin() const noexcept;
          \end{cpp}
    \item \cppinline{array::cbegin()}：返回数组中第一个元素的const迭代器。
    \item \cppinline{array::cend()}：返回数组中最后一个元素的迭代器。
    \item \cppinline{array::crbegin()}：返回reverse数组后第一个元素的迭代器。
    \item \cppinline{array::cend()}：返回数组reverse后最后一个元素的迭代器。
    \item \cppinline{array::data()}：返回数组中第一个元素的指针(可以不像迭代器一样能跳跃访问)。
    \item \cppinline{array::empty()}：如果array容器为空返回true，否则返回false。
    \item \cppinline{array::end()}：返回array中指向最后一个元素后一个元素的迭代器。
    \item \cppinline{array::fill(const value_type&val)}：设置val作为array对象的值。
    \item \cppinline{array::front()}：返回array容器中第一个元素的引用。
    \item \cppinline{array::max_size()}：返回array能包含的元素的最大数量。
    \item \cppinline{array::operator[  ]}：重载[  ]操作，能像c++数组一样访问array元素。
    \item \cppinline{array::rbegin()}：返回反向后指向第一个元素的迭代器。
    \item \cppinline{array::rend()}：返回反向后指向最后一个元素的迭代器。
    \item \cppinline{array::size()}：返回array中templete指定类型的元素的个数。
    \item \cppinline{array::swap()}：交换两个array对象中元素，array对象的元素类型和元素个素相同。
\end{itemize}
\subsection{deque}
\begin{itemize}
    \item
          \begin{itemize}
              \item \cppinline{deque::assign(beg,end)}：将[beg; end)区间中的数据赋值给deque。
              \item \cppinline{deque::assign(n,elem)}：将n个elem的拷贝赋值给deque。
          \end{itemize}
    \item \cppinline{deque::at(idx)}：返回索引idx所指的数据，如果idx越界，抛出out\_of\_range。
    \item \cppinline{deque::back()}：返回最后一个数据，不检查这个数据是否存在。
    \item \cppinline{deque::begin()}：返回指向迭代器中的一个元素的迭代器。
    \item \cppinline{deque::cbegin()}：返回指向迭代器中的一个const元素的迭代器。
    \item \cppinline{deque::clear()}：移除容器中所有数据。
    \item \cppinline{deque::crbegin()}：返回反向队列后指向迭代器中的第一个const元素的迭代器。
    \item 构造函数：
          \begin{itemize}
              \item  \cppinline{deque()}： 创建一个空的deque。
              \item  \cppinline{deque::(c2)}：复制一个deque。
              \item  \cppinline{deque(n)} ：创建一个deque，含有n个数据，数据均已缺省构造产生。
              \item  \cppinline{deque(n, elem)}：创建一个含有n个elem拷贝的deque。
              \item  \cppinline{deque(beg,end)}：创建一个以[beg;end)区间的deque。
          \end{itemize}
    \item \cppinline{~deque<Elem>()}：销毁所有数据，释放内存。
    \item \cppinline{deque::crend}：返回deque反向后指向最后一个元素的迭代器。
    \item \cppinline{deque::emplace()}：插入一个新的元素args到position位置。返回一个迭代器。\textbf{函数原型:}
          \mint{cpp}{template <class... Args>iterator emplace (const_iterator position, Args&&... args);}
    \item deque::emplace\_back():插入一个元素到队尾。\\
          \textbf{函数原型}\\
          \cppinline{template <class... Args>
              void emplace_back (Args&&... args);}
    \item \cppinline{deque::empalce_front}：插入一个元素到队头。函数原型：
          \mint{cpp}{template <class... Args> void emplace_back (Args&&... args);}
    \item \cppinline{deque::empty()}： 判断容器是否为空。
    \item \cppinline{deque::end()}：指向迭代器中的最后一个数据地址。
    \item
          \begin{itemize}
              \item \cppinline{deque::erase(pos)}：删除pos位置的数据，返回下一个数据的位置。
              \item \cppinline{deque::erase(beg,end)}：删除[beg,end)区间的数据，返回下一个数据的位置。
          \end{itemize}
    \item \cppinline{deque::front()}：返回第一个数据。
    \item \cppinline{dqueue::get_allocator}：使用构造函数返回一个拷贝。
    \item 插入：
          \begin{itemize}
              \item \cppinline{deque::insert(pos,elem)}： 在pos位置插入一个elem拷贝，返回新数据位置。
              \item \cppinline{deque::insert(pos,n,elem)}：在pos位置插入>n个elem数据。无返回值。
              \item \cppinline{deque::insert(pos,beg,end)}：在pos位置插入在[beg,end)区间的数据。无返回值。
          \end{itemize}
    \item \cppinline{deque::max_size()}：返回容器中最大数据的数量。
    \item \cppinline{deque::pop_back()}： 删除最后一个数据。
    \item \cppinline{deque::pop_front()}：删除头部数据。
    \item \cppinline{deque::push_back(elem)}：在尾部加入一个数据。
    \item \cppinline{deque::push_front(elem)}：在头部插入一个数据。
    \item \cppinline{deque::rbegin()}：返回一个逆向队列的第一个数据。
    \item \cppinline{deque::rend()}：返回一个逆向队列的最后一个数据的下一个位置。
    \item \cppinline{deque::resize(num)}：重新指定队列的长度。
    \item \cppinline{deque::shrink_to_fit}：要求容器减小存储满足它的大小。
    \item \cppinline{deque::size()}：返回容器中实际数据的个数。
    \item \cppinline{C1.swap(c2)}：将c1和c2元素互换。Swap(c1,c2) 同上操作。
\end{itemize}
\subsection{forward\_list}
std::forward\_list是在C++11中引入的单向链表或叫正向列表。forward\_list具有插入、删除表项速度快、消耗内存空间少的特点，但只能向前遍历。与其它序列容器(array、vector、deque)相比，forward\_list在容器内任意位置的成员的插入、提取(extracting)、移动、删除操作的速度更快，因此被广泛用于排序算法。forward\_list是一个允许在序列中任何一处位置以常量耗时插入或删除元素的顺序容器(sequence container)。forward\_list可以看作是对C语言风格的单链表的封装，仅提供有限的接口，和C中它的实现相比，基本上不会有任何开销。当不需要双向迭代的时候，与std::list相比，该容器具有更高的空间利用率。

forward\_list的主要缺点是不能在常量时间内随机访问任意成员，对成员的访问需要线性时间代价；以及存储链接信息需要消耗内存，特别是当包含大量的小规模成员时。forward\_list处于效率考虑，有意不提供size()成员函数。获取forward\_list所包含的成员个数需要用std::distance(\_begin, \_end)算法。forward\_list中的每个元素保存了定位前一个元素及后一个元素的信息，不能进行直接随机访问操作。
\begin{itemize}
    \item \cppinline{forward_list::assign()}：赋值替换全部内容。
    \item \cppinline{forward_list::before_begin}：返回开始位置之前的迭代器。
    \item \cppinline{forward_list::begin()}：返回指向开始位置的迭代器。
    \item \cppinline{forward_list::cbefore_begin()}：返回指向开始位置之前的const迭代器。
    \item \cppinline{forward_list::cbegin()}: 返回指向开始位置的const迭代器。
    \item \cppinline{forward_list::cend()}: 返回指向结束位置的const迭代器。
    \item \cppinline{forward_list::clear()}：清空链表的内容。
    \item \cppinline{forward_list::emplace_after()}：清空链表的内容。在position后面插入一个新的元素到emplace\_after。函数原型：
          \mint{cpp}{template <class... Args> iterator emplace_after (const_iterator position, Args&&... args);}
    \item \cppinline{forward_list::emplace_front()}：在链表头部原位构造新的成员并插入到链表最开始处。
    \item \cppinline{forward_list::empty()}：测试容器是否为空。
    \item \cppinline{forward_list::end()}：返回指向结束位置的迭代器。
    \item \cppinline{forward_list::emplace_after()}：在当前位置的尾方向原位插入元素。
    \item \cppinline{forward_list::front()}：返回第一个成员的引用。
    \item \cppinline{forward_list:: get_allocator()}：获取当前的分配器。
    \item \cppinline{forward_list::insert_after()}：在当前位置的尾方向插入成员，可译为拷贝语义、移动语义、值被插入多次、插入一个序列、插入初始化器的内容。
    \item \cppinline{forward_list::max_size()}：返回容器的可能允许的最大容量。
    \item \cppinline{forward_list:: merge()}：两个已经有序的链表做有序合并。
    \item \cppinline{forward_list::pop_front()}：删除链表头部元素。
    \item \cppinline{forward_list::push_front()}：在链表头部插入元素，使用拷贝语义或移动语义。
    \item \cppinline{forward_list:: remove()}：删除（析构）具有特定内容的成员。
    \item \cppinline{forward_list:: remove_if()}：删除使谓词为真的成员。
          \begin{cpp}
              // forward_list::remove_if
              #include <iostream>
              #include <forward_list>

              // a predicate implemented as a function:
              bool single_digit (const int& value) { return (value<10); }

              // a predicate implemented as a class:
              class is_odd_class
              {
              public:
              bool operator() (const int& value) {return (value%2)==1; }
                  } is_odd_object;

              int main ()
              {
              std::forward_list<int> mylist = {7, 80, 7, 15, 85, 52, 6};

              mylist.remove_if (single_digit);      // 80 15 85 52

              mylist.remove_if (is_odd_object);     // 80 52

              std::cout << "mylist contains:";
              for (int& x: mylist) std::cout << ' ' << x;
              std::cout << '\n';

              return 0;
              }
          \end{cpp}
          输出：
          \begin{bash}
              mylist contains: 80 52
          \end{bash}
    \item \cppinline{forward_list::resize()}：改变链表的容量。
    \item \cppinline{forward_list:: reverse()}：把一个链表所有成员逆序。
    \item \cppinline{forward_list:: sort()}：对一个链表的成员做稳定排序，要求是strict weak ordering谓词。
    \item \cppinline{forward_list::splice_after()}：把另一个链表的单个成员、或子序列、或整个序列，移动插入到当前链表指定位置之后。
          \begin{cpp}
              #include <iostream>
              #include <forward_list>

              int main ()
              {
              std::forward_list<int> first = { 1, 2, 3 };
              std::forward_list<int> second = { 10, 20, 30 };

              auto it = first.begin();  // points to the 1

              first.splice_after ( first.before_begin(), second );
              // first: 10 20 30 1 2 3
              // second: (empty)
              // "it" still points to the 1 (now first's 4th element)

              second.splice_after ( second.before_begin(), first, first.begin(), it);
              // first: 10 1 2 3
              // second: 20 30

              first.splice_after ( first.before_begin(), second, second.begin() );
              // first: 30 10 1 2 3
              // second: 20
              // * notice that what is moved is AFTER the iterator

              std::cout << "first contains:";
              for (int& x: first) std::cout << " " << x;
              std::cout << std::endl;

              std::cout << "second contains:";
              for (int& x: second) std::cout << " " << x;
              std::cout << std::endl;

              return 0;
              }
          \end{cpp}
          输出：
          \begin{bash}
              first contains: 30 10 1 2 3
              second contains: 20
          \end{bash}
    \item \cppinline{forward_list::swap()}：交换两个链表的内容。
    \item \cppinline{forward_list:: unique()}：删除与序列中前一个成员相等（或者二元谓词为真）的成员。特别适用于排序后链表。
          \begin{cpp}
              // forward_list::unique
              #include <iostream>
              #include <cmath>
              #include <forward_list>

              // a binary predicate implemented as a function:
              bool same_integral_part (double first, double second)
              { return ( int(first)==int(second) ); }

              // a binary predicate implemented as a class:
              class is_near_class
              {
              public:
              bool operator() (double first, double second)
              { return (fabs(first-second)<5.0); }
              } is_near_object;

              int main ()
              {

              std::forward_list<double> mylist = { 15.2, 73.0, 3.14, 15.85, 69.5,
              73.0, 3.99, 15.2, 69.2,  18.5 };

              mylist.sort();                       //   3.14,  3.99, 15.2, 15.2, 15.85
              //  18.5,  69.2,  69.5, 73.0, 73.0

              mylist.unique();                     //   3.14,  3.99, 15.2, 15.85
              //  18.5,  69.2,  69.5, 73.0

              mylist.unique (same_integral_part);  //  3.14, 15.2, 18.5,  69.2, 73.0

              mylist.unique (is_near_object);      //  3.14, 15.2, 69.2

              std::cout << "mylist contains:";
              for (double& x: mylist) std::cout << ' ' << x;
              std::cout << '\n';

              return 0;
              }
          \end{cpp}
          输出：
          \begin{bash}
              mylist contains: 3.14 15.2 69.2
          \end{bash}
\end{itemize}
forword\_list例子：
\cppfile{code/STL/forword_list_demo.cxx}
\subsection{\href{http://www.cplusplus.com/reference/list/list/}{list}}
list（双端链表）和forward\_list（单链表）。
\begin{itemize}
    \item \cppinline{list::assign}：给链表赋值。
          \begin{cpp}
              #include <list>
              #include <vector>
              #include <iostream>

              using namespace std;

              int main(int argc, char *argv[]) {
              vector<int> vec = vector<int>(3, 100);
              list<int> li1;
              list<int> li2;
              list<int> li3;
              // 通过其他容器赋值
              li1.assign(vec.begin(), vec.end());
              // 直接赋值
              li2.assign(3, 100);
              // 从数值赋值
              int c[] = {1, 2, 4, 3};
              li3.assign(c, c + 4);
              for (auto i:li3) {
                      cout << i << " " << endl;
                  }

              }
          \end{cpp}
    \item \cppinline{list::back}：获取list最后一个元素的引用。
    \item \cppinline{list::begin}：获取list第一个元素的迭代器。
    \item \cppinline{list::cbegin}：获取list第一个元素的常数迭代器。
    \item \cppinline{list::cend}：获取list最后一个元素的常数迭代器。
    \item \cppinline{list::emplace}：在list指定位置插入新的元素。
    \item \cppinline{list:emplace_back}：在list末尾插入新的元素。
    \item \cppinline{list::emplace_front}：在list开头插入新的元素。
    \item \cppinline{list::empty}：判断list是否为空。
    \item \cppinline{list:end}：指向list最后一个元素后一个元素的迭代器。
    \item \cppinline{list::erase}：删除list中的元素。
          \begin{cpp}
              // erasing from list
              #include <iostream>
              #include <list>

              int main ()
              {
                      std::list<int> mylist;
                      std::list<int>::iterator it1,it2;

                      // set some values:
                      for (int i=1; i<10; ++i) mylist.push_back(i*10);

                      // 10 20 30 40 50 60 70 80 90
                      it1 = it2 = mylist.begin(); // ^^
                      advance (it2,6);            // ^                 ^
                      ++it1;                      //    ^              ^

                      it1 = mylist.erase (it1);   // 10 30 40 50 60 70 80 90
                      //    ^           ^

                      it2 = mylist.erase (it2);   // 10 30 40 50 60 80 90
                      //    ^           ^

                      ++it1;                      //       ^        ^
                      --it2;                      //       ^     ^

                      mylist.erase (it1,it2);     // 10 30 60 80 90
                      //        ^

                      std::cout << "mylist contains:";
                      for (it1=mylist.begin(); it1!=mylist.end(); ++it1)
                      std::cout << ' ' << *it1;
                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{list::front}：获取list地一个元素。
    \item \cppinline{list::get_allocator}:\cppinline{allocator_type} 类型的分配器。
          \begin{cpp}
              // list::get_allocator
              #include <iostream>
              #include <list>

              int main ()
              {
                      std::list<int> mylist;
                      int * p;

                      // allocate an array of 5 elements using mylist's allocator:
                      p=mylist.get_allocator().allocate(5);

                      // assign some values to array
                      for (int i=0; i<5; ++i) p[i]=i;

                      std::cout << "The allocated array contains:";
                      for (int i=0; i<5; ++i) std::cout << ' ' << p[i];
                      std::cout << '\n';

                      mylist.get_allocator().deallocate(p,5);

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{list::insert}：在list中插入元素。
    \item \cppinline{list::max_size}：list的最大长度。
    \item \cppinline{list::merge}：合并两个list。
    \item \cppinline{list::operator=}：lilist赋值。
    \item \cppinline{list::pop_back}：删除list末尾的元素。
    \item \cppinline{list::pop_front}：删除list开头的元素。
    \item \cppinline{list::push_back}：添加新的元素到list末尾。
    \item \cppinline{list::push_front}：添加新的元素到list的开头。
    \item \cppinline{list::rbegin}：指向list末尾的迭代器。
    \item \cppinline{list::remove}：删除list的元素。
    \item \cppinline{list::remove_if}：按照条件删除list元素。
          \begin{cpp}
              // list::remove_if
              #include <iostream>
              #include <list>

              // a predicate implemented as a function:
              bool single_digit (const int& value) { return (value<10); }

              // a predicate implemented as a class:
              struct is_odd {
              bool operator() (const int& value) { return (value%2)==1; }
                  };

              int main ()
              {
                      int myints[]= {15,36,7,17,20,39,4,1};
                      std::list<int> mylist (myints,myints+8);   // 15 36 7 17 20 39 4 1

                      mylist.remove_if (single_digit);           // 15 36 17 20 39

                      mylist.remove_if (is_odd());               // 36 20

                      std::cout << "mylist contains:";
                      for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
                      std::cout << ' ' << *it;
                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{list::rend}：指向list的开头的迭代器。
    \item \cppinline{list::resize}：resize list的大小
    \item \cppinline{list::reverse}：反转list。
    \item \cppinline{list::size}：list的大小。
    \item \cppinline{list::sort}：排序list。
    \item \cppinline{list::slice}：
          \begin{cpp}
              // splicing lists
              #include <iostream>
              #include <list>

              int main ()
              {
                      std::list<int> mylist1, mylist2;
                      std::list<int>::iterator it;

                      // set some initial values:
                      for (int i=1; i<=4; ++i)
                      mylist1.push_back(i);      // mylist1: 1 2 3 4

                      for (int i=1; i<=3; ++i)
                      mylist2.push_back(i*10);   // mylist2: 10 20 30

                      it = mylist1.begin();
                      ++it;                         // points to 2

                      mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4
                      // mylist2 (empty)
                      // "it" still points to 2 (the 5th element)

                      mylist2.splice (mylist2.begin(),mylist1, it);
                      // mylist1: 1 10 20 30 3 4
                      // mylist2: 2
                      // "it" is now invalid.
                      it = mylist1.begin();
                      std::advance(it,3);           // "it" points now to 30

                      mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
                      // mylist1: 30 3 4 1 10 20

                      std::cout << "mylist1 contains:";
                      for (it=mylist1.begin(); it!=mylist1.end(); ++it)
                      std::cout << ' ' << *it;
                      std::cout << '\n';

                      std::cout << "mylist2 contains:";
                      for (it=mylist2.begin(); it!=mylist2.end(); ++it)
                      std::cout << ' ' << *it;
                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{list::swap}：交换两个list中的元素。
    \item \cppinline{list::unique}：对list中的元素去重。
          \begin{cpp}
              // list::unique
              #include <iostream>
              #include <cmath>
              #include <list>

              // a binary predicate implemented as a function:
              bool same_integral_part (double first, double second)
              { return ( int(first)==int(second) ); }

              // a binary predicate implemented as a class:
              struct is_near {
              bool operator() (double first, double second)
              { return (fabs(first-second)<5.0); }
              };

              int main ()
              {
                      double mydoubles[]={ 12.15,  2.72, 73.0,  12.77,  3.14,
                              12.77, 73.35, 72.25, 15.3,  72.25 };
                      std::list<double> mylist (mydoubles,mydoubles+10);

                      mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,
                      // 15.3,  72.25, 72.25, 73.0,  73.35

                      mylist.unique();           //  2.72,  3.14, 12.15, 12.77
                      // 15.3,  72.25, 73.0,  73.35

                      mylist.unique (same_integral_part);  //  2.72,  3.14, 12.15
                      // 15.3,  72.25, 73.0

                      mylist.unique (is_near());           //  2.72, 12.15, 72.25

                      std::cout << "mylist contains:";
                      for (std::list<double>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
                      std::cout << ' ' << *it;
                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
\end{itemize}
list例子：
\cppfile{code/STL/list_demo.cxx}
\subsection{map}
C++中map提供的是一种键值对容器，里面的数据都是成对出现的,如下图：每一对中的第一个值称之为关键字(key)，每个关键字只能在map中出现一次；第二个称之为该关键字的对应值。
\begin{itemize}
    \item \cppinline{map::at()}：返回key k对应的值。
          \cppfile{code/STL/map1/main.cpp}
    \item \cppinline{map::begin()}：返回一个访问map容器中第一个元素的迭代器。
          \cppfile{code/STL/map2/main.cpp}
    \item \cppinline{map::cbegin()}：返回一个指向map容器中第一个const的迭代器。
    \item \cppinline{map::cend()}：返回一个指向map容器中最后一个const的迭代器。
    \item \cppinline{map::clear()}：移除map容器中所有的元素。
    \item \cppinline{map::count()}：统计map容器中key的元素的数量。
          \cppfile{code/STL/map3/main.cpp}
    \item \cppinline{map::crbegin()}：返回指向容器中最后一个常量元素的迭代器(reverse后的第一个)。
          \cppfile{code/STL/map4/main.cpp}
    \item \cppinline{map::crend()}：返回指向容器中第一个常量元素的迭代器(reverse后的第一个)。
    \item \cppinline{map::emplace()}：如果k不同，插入一个新的元素到map容器。
          \begin{remark}
              当调用push或insert成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。
          \end{remark}
          \cppfile{code/STL/map4/main.cpp}
    \item \cppinline{map::emplace_hint()}：如果key是独一无二的，插入一个元素到map。和上面的函数不同在于可以构造元素插入。
          \cppfile{code/STL/map6/main.cpp}
    \item \cppinline{map::empty()}：检查容器是否为空，元素数为0时返回true，否则返回false
    \item \cppinline{map::end()}：返回map容器最后一个元素的迭代器。
    \item \cppinline{map::find( const Key& key )}寻找带有特定键的元素
    \item 返回一个结合map的allocator对象的拷贝。
          \cppfile{code/STL/map7/main.cpp}
    \item 插入：
          \begin{cpp}
              insert( const value_type& value )
              insert( P&& value )
              insert( const_iterator hint, const value_type& value )
              insert( const_iterator hint, P&& value )
              insert( InputIt first, InputIt last )
              insert( std::initializer_list<value_type> ilist )
          \end{cpp}
    \item \cppinline{key_comp()}：返回用于比较键的函数。
          \cppfile{code/STL/ex4/main.cpp}
    \item \cppinline{map::lower_bound( const Key& key )}：返回指向首个不小于给定键的元素的迭代器。
          \cppfile{code/STL/map9/main.cpp}
    \item \cppinline{map::max_size()}：返回可容纳的最大元素数
    \item \cppinline{map::rbegin}：返回reverse后的指向第一个元素的迭代器。
    \item \cppinline{map::rend}:返回reverse后的指向最后一个元素的迭代器。
    \item \cppinline{map::swap( map& other )}：交换内容。
          \cppfile{code/STL/map10/main.cpp}
    \item \cppinline{map::upper_bound( const Key& key )}：返回指向首个大于给定键的元素的迭代器。
          \cppfile{code/STL/map11/main.cpp}
    \item \cppinline{map::value_comp()}    返回用于在value\_type类型的对象中比较键的函数。
          \cppfile{code/STL/map12/main.cpp}
\end{itemize}
\subsection{queue}
\begin{itemize}
    \item \cppinline{queue::empty}：测试队列是否为空。
    \item \cppinline{queue::size}：返回队列的长度
    \item \cppinline{queue::front}：访问下一个元素。
          \cppfile{code/STL/stack1/main.cpp}
    \item \cppinline{queue::back}：访问最后一个元素。
    \item \cppinline{queue::push}：插入一个元素到队列。
    \item \cppinline{queue::emplace}：构造插入一个元素到队列。
          \cppfile{code/STL/stack2/main.cpp}
    \item \cppinline{queue::pop}：删除下一个元素
          \cppfile{code/STL/stack3/main.cpp}
    \item  \cppinline{queue::swap}：交换队列的内容。
\end{itemize}
\cppfile{code/STL/stack4/main.cpp}
\subsection{\href{http://www.cplusplus.com/reference/set/set/}{set}}
set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

terator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push\_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其它内存覆盖或者内存已经被释放了。即使时push\_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。

\begin{itemize}
    \item   \cppinline{set::begin()}：返回set容器的第一个元素。
    \item   \cppinline{set::cbegin()}：返回set容器的第一个const元素。
    \item   \cppinline{set::clear()}：删除set容器中的所有的元素
    \item   \cppinline{set::count()}：用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。
    \item   \cppinline{set::crbegin()}：返回set容器reverse后的第一个const元素。
    \item   \cppinline{set::cend()}：返回set容器的最后一个const元素。
    \item   \cppinline{set::emplace()}:插入一个元素到set，如果元素是独一无二的，新元素使用args作为参数用于这个构造体。\\
          \textbf{函数原型：}
          \cppinline{template <class... Args>
              pair<iterator,bool> emplace (Args&&... args);}
          \begin{cpp}
              // set::emplace
              #include <iostream>
              #include <set>
              #include <string>

              int main ()
              {
                      std::set<std::string> myset;

                      myset.emplace("foo");
                      myset.emplace("bar");
                      auto ret = myset.emplace("foo");

                      if (!ret.second) std::cout << "foo already exists in myset\n";

                      return 0;
                  }
          \end{cpp}
    \item   set::emplace\_hint():插入一个新的元素在set，如果是独一无二的默认在position位置插入。新元素使用args作为参数用于构造体
          \begin{cpp}
              // set::emplace_hint
              #include <iostream>
              #include <set>
              #include <string>

              int main ()
              {
                      std::set<std::string> myset;
                      auto it = myset.cbegin();

                      myset.emplace_hint (it,"alpha");
                      it = myset.emplace_hint (myset.cend(),"omega");
                      it = myset.emplace_hint (it,"epsilon");
                      it = myset.emplace_hint (it,"beta");

                      std::cout << "myset contains:";
                      for (const std::string& x: myset)
                      std::cout << ' ' << x;
                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
    \item   set::empty()：判断set容器是否为空。
    \item   set::end()：返回set容器的最后一个元素。
    \item   set::equal\_range() ：返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于end()的值。
    \item   set::erase(iterator)：删除定位器iterator指向的值
    \item   set::erase(first,second)：删除定位器first和second之间的值
    \item   set::erase(key\_value)：删除键值key\_value的值
    \item   set::find()  ，返回给定值的定位器，如果没找到则返回end()。
    \item   set::get\_allocator：
    \item   set::insert(key\_value); 将key\_value插入到set中 ，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key\_value已经在set中，则iterator表示的key\_value在set中的位置。
    \item   set::inset(first,second);将定位器first到second之间的元素插入到set中，返回值是void。
    \item   set::key\_comp:返回一个比较对象的拷贝。
          \begin{cpp}
              // set::key_comp
              #include <iostream>
              #include <set>

              int main ()
              {
                      std::set<int> myset;
                      int highest;

                      std::set<int>::key_compare mycomp = myset.key_comp();

                      for (int i=0; i<=5; i++) myset.insert(i);

                      std::cout << "myset contains:";

                      highest=*myset.rbegin();
                      std::set<int>::iterator it=myset.begin();
                      do {
                              std::cout << ' ' << *it;
                          } while ( mycomp(*(++it),highest) );

                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
    \item   set::lower\_bound(key\_value)：返回第一个大于等于key\_value的定位器
    \item   set::max\_size()：返回set容器可能包含的元素最大个数
    \item   set::rbegin()：返回的值和end()相同
    \item   set::rend()：返回的值和rbegin()相同
    \item   set::size()：返回当前set容器中的元素个数
    \item   set::upper\_bound(key\_value)：返回最后一个大于等于key\_value的定位器
    \item   set::value\_comp：函数将返回相同的功能的函数对象。
          \begin{cpp}
              // set::value_comp
              #include <iostream>
              #include <set>

              int main ()
              {
                      std::set<int> myset;

                      std::set<int>::value_compare mycomp = myset.value_comp();

                      for (int i=0; i<=5; i++) myset.insert(i);

                      std::cout << "myset contains:";

                      int highest=*myset.rbegin();
                      std::set<int>::iterator it=myset.begin();
                      do {
                              std::cout << ' ' << *it;
                          } while ( mycomp(*(++it),highest) );

                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
\end{itemize}
\subsection{\href{http://www.cplusplus.com/reference/stack/stack/}{stack}}
\begin{itemize}
    \item
          \begin{cpp}
              explicit stack (const container_type& ctnr);
              explicit stack (container_type&& ctnr = container_type());
              template <class Alloc> explicit stack (const Alloc& alloc);
              template <class Alloc> stack (const container_type& ctnr, const Alloc& alloc);
              template <class Alloc> stack (container_type&& ctnr, const Alloc& alloc);
              template <class Alloc> stack (const stack& x, const Alloc& alloc);
              template <class Alloc> stack (stack&& x, const Alloc& alloc);
          \end{cpp}
          \begin{cpp}
              // constructing stacks
              #include <iostream>       // std::cout
              #include <stack>          // std::stack
              #include <vector>         // std::vector
              #include <deque>          // std::deque

              int main ()
              {
                      std::deque<int> mydeque (3,100);          // deque with 3 elements
                      std::vector<int> myvector (2,200);        // vector with 2 elements

                      std::stack<int> first;                    // empty stack
                      std::stack<int> second (mydeque);         // stack initialized to copy of deque

                      std::stack<int,std::vector<int> > third;  // empty stack using vector
                      std::stack<int,std::vector<int> > fourth (myvector);

                      std::cout << "size of first: " << first.size() << '\n';
                      std::cout << "size of second: " << second.size() << '\n';
                      std::cout << "size of third: " << third.size() << '\n';
                      std::cout << "size of fourth: " << fourth.size() << '\n';

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{stack::emplace()}：添加一个新元素到栈顶。函数原型：
          \mint{cpp}{template <class... Args> void emplace (Args&&... args);}
          \begin{cpp}
              // stack::emplace
              #include <iostream>       // std::cin, std::cout
              #include <stack>          // std::stack
              #include <string>         // std::string, std::getline(string)

              int main ()
              {
                      std::stack<std::string> mystack;

                      mystack.emplace ("First sentence");
                      mystack.emplace ("Second sentence");

                      std::cout << "mystack contains:\n";
                      while (!mystack.empty())
                      {
                              std::cout << mystack.top() << '\n';
                              mystack.pop();
                          }

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{stack::empty()}：返回栈是否为空，如果size为0则返回false否则返回true。
    \item \cppinline{stack::pop()}：删除栈顶元素。
          \begin{cpp}
              // stack::push/pop
              #include <iostream>       // std::cout
              #include <stack>          // std::stack

              int main ()
              {
                      std::stack<int> mystack;

                      for (int i=0; i<5; ++i) mystack.push(i);

                      std::cout << "Popping out elements...";
                      while (!mystack.empty())
                      {
                              std::cout << ' ' << mystack.top();
                              mystack.pop();
                          }
                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{stack::push()}：压入一个新元素到栈顶新元素被初始化为val。函数原型:
          \begin{cpp}
              void push (const value_type& val);
              void push (value_type&& val);
          \end{cpp}
          \begin{cpp}
              // stack::push/pop
              #include <iostream>       // std::cout
              #include <stack>          // std::stack

              int main ()
              {
                      std::stack<int> mystack;

                      for (int i=0; i<5; ++i) mystack.push(i);

                      std::cout << "Popping out elements...";
                      while (!mystack.empty())
                      {
                              std::cout << ' ' << mystack.top();
                              mystack.pop();
                          }
                      std::cout << '\n';

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{stack::size()}：返回栈中元素的个数。
    \item \cppinline{stack::swap()}：交换两个栈中的内容。
          \begin{cpp}
              // stack::swap
              #include <iostream>       // std::cout
              #include <stack>          // std::stack

              int main ()
              {
                      std::stack<int> foo,bar;
                      foo.push (10); foo.push(20); foo.push(30);
                      bar.push (111); bar.push(222);

                      foo.swap(bar);

                      std::cout << "size of foo: " << foo.size() << '\n';
                      std::cout << "size of bar: " << bar.size() << '\n';

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{stack::top()}：返回栈顶元素的引用。
          \begin{cpp}
              // stack::top
              #include <iostream>       // std::cout
              #include <stack>          // std::stack

              int main ()
              {
                      std::stack<int> mystack;

                      mystack.push(10);
                      mystack.push(20);

                      mystack.top() -= 5;

                      std::cout << "mystack.top() is now " << mystack.top() << '\n';

                      return 0;
                  }
          \end{cpp}
\end{itemize}

\subsection{\href{http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue}{priority\_queue}}
\begin{itemize}
    \item priority\_queue::umplace():添加一个新元素到priority\_queue,新元素通过args构造。函数原型如下：
          \begin{cpp}
              template <class... Args> void emplace (Args&&... args);
          \end{cpp}
          \cppfile{code/STL/queue1/main.cpp}
    \item \cppinline{priority_queue::empty()}：判断优先队列是否为空。
    \item \cppinline{priority_queue::pop()}：获取优先队列中最高优先级的元素删除。
    \item priority\_queue::push：插入一个新的元素到优先队列中，队列中的元素初始化为val。函数原型如下：
          \begin{cpp}
              void push (const value_type& val);
              void push (value_type&& val);
          \end{cpp}
          \cppfile{code/STL/queue2/main.cpp}
    \item priority\_queue::size:返回优先队列中包含的元素个数。
    \item std::priority\_queue::swap：交换优先队列中的元素。
          \cppfile{code/STL/queue3/main.cpp}
    \item priority\_queue::top:返回top元素的const引用。
          \cppfile{code/STL/queue4/main.cpp}
\end{itemize}
\subsection{\href{http://www.cplusplus.com/reference/unordered_map/unordered_map/}{unorder\_map}}
\textbf{函数模板：}
\begin{cpp}
    template < class Key,                                    // unordered_map::key_type
    class T,                                      // unordered_map::mapped_type
    class Hash = hash<Key>,                       // unordered_map::hasher
    class Pred = equal_to<Key>,                   // unordered_map::key_equal
    class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
    > class unordered_map;
\end{cpp}
\begin{table}[H]
    \centering
    \begin{tabular}{p{0.2\textwidth}p{0.4\textwidth}p{0.4\textwidth}}
        \toprule
        成员类型               & 定义                                    & 注意                                          \\
        \midrule
        key\_type              & the first template parameter (Key)      &                                               \\
        mapped\_type           & the second template parameter (T)       &                                               \\
        value\_type            & pair<const key\_type,mapped\_type>      &                                               \\
        hasher                 & the third template parameter (Hash)     & defaults to: hash<key\_type>                  \\
        key\_equal             & the fourth template parameter (Pred)    & defaults to: equal\_to<key\_type>             \\
        allocator\_type        & the fifth template parameter (Alloc)    & defaults to: allocator<value\_type>           \\
        reference              & Alloc::reference                        &                                               \\
        const\_reference       & Alloc::const\_reference                 &                                               \\
        pointer                & Alloc::pointer                          & for the default allocator: value\_type*       \\
        const\_pointer         & Alloc::const\_pointer                   & for the default allocator: const value\_type* \\
        iterator               & a forward iterator to value\_type       &                                               \\
        const\_iterator        & a forward iterator to const value\_type &                                               \\
        local\_iterator        & a forward iterator to value\_type       &                                               \\
        const\_local\_iterator & a forward iterator to const value\_type &                                               \\
        size\_type             & an unsigned integral type               & usually the same as size\_t                   \\
        difference\_type       & a signed integral type                  & usually the same as ptrdiff\_t                \\
        \bottomrule
    \end{tabular}
\end{table}
\begin{itemize}
    \item \cppinline{unordered_map::at}:很据key获得访问元素的引用，如果key不匹配容器里面的任何类型将抛出 out\_of\_range exception
          \cppfile{code/STL/order_map1/main.cpp}
    \item \cppinline{unordered_map::begin}：获得容器第一个元素的指针或者第一个bucket元素。
          \cppfile{code/STL/unorder_map1/main.cpp}
    \item \cppinline{unordered_map::bucket}:返回key为k的元素bucket号。一个bucket是一个slot，在原素内部hash表根据它们的hash值赋值，bucket号从0到bucket\_count-1。
          \cppfile{code/STL/unorder_map2/main.cpp}

    \item \cppinline{unordered_map::bucket_count}:返回在unordered\_map容器中的bucket数量
          \cppfile{code/STL/unorder_map3/main.cpp}

    \item \cppinline{unordered_map::bucket_size}:返回bucket n中的元素数目。
          \cppfile{code/STL/unorder_map4/main.cpp}

    \item \cppinline{unordered_map::cbegin}:返回指向容器中的第一个const元素或者bucket中的const元素。
          \cppfile{code/STL/unorder_map5/main.cpp}
    \item \cppinline{unordered_map::cend}:返回指向容器或者bucket中最后一个元素的const迭代器。
    \item \cppinline{unordered_map::clear}:删除容器中所有的元素。
          \cppfile{code/STL/unorder_map6/main.cpp}

    \item \cppinline{unordered_map::count}:返回容器中key出现的次数。
          \cppfile{code/STL/unorder_map7/main.cpp}

    \item 函数原型：
          \begin{cpp}
              template <class... Args>
              pair<iterator, bool> emplace ( Args&&... args );
          \end{cpp}
          如果它的key是独一无二的，将新元素插入args指定的位置。
          \cppfile{code/STL/unorder_map8/main.cpp}

    \item \cppinline{unordered_map::emplace_hint}:如果key独一无二，将元素插入容器。position指向它的插入指针开始搜索的位置。函数原型如下：
          \begin{cpp}
              template <class... Args>
              iterator emplace_hint ( const_iterator position, Args&&... args );
          \end{cpp}
    \item \cppinline{unordered_map::empty}:返回容器是否为空的bool值。
    \item \cppinline{unordered_map::end}：返回指向容器最后一个元素的后一个元素的指针。
    \item \cppinline{unordered_map::equal_range}：返回key等于k的所有元素的范围。
    \item \cppinline{std::unordered_map::erase}：移除指定元素或者指定范围的元素。
          \cppfile{code/STL/unorder_map9/main.cpp}

    \item \cppinline{unordered_map::find}:搜索key返回找到的迭代器否则返回end迭代器。
          \cppfile{code/STL/unorder_map10/main.cpp}

    \item \cppinline{unordered_map::get_allocator}:返回allocator给容器的构造对象。
    \item \cppinline{unordered_map::hash_function}:返回容器的hash函数对象。
          \cppfile{code/STL/unorder_map11/main.cpp}
    \item \cppinline{unordered_map::insert}：仅当插入元素的key不存在于容器时插入容器。
          \cppfile{code/STL/unorder_map12/main.cpp}

    \item \cppinline{unordered_map::key_eq}：返回key是否相等的预测结果。
          \begin{cpp}
              // unordered_map::key_eq
              #include <iostream>
              #include <string>
              #include <unordered_map>

              int main ()
              {
                      std::unordered_map<std::string,std::string> mymap;

                      bool case_insensitive = mymap.key_eq()("test","TEST");

                      std::cout << "mymap.key_eq() is ";
                      std::cout << ( case_insensitive ? "case insensitive" : "case sensitive" );
                      std::cout << std::endl;

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{unordered_map::load_factor}：返回容器的负载因子$load_{factor} = \frac{size}{bucket_{count}}$ 。
          \begin{cpp}
              // unordered_map hash table stats
              #include <iostream>
              #include <unordered_map>

              int main ()
              {
                      std::unordered_map<int,int> mymap;

                      std::cout << "size = " << mymap.size() << std::endl;
                      std::cout << "bucket_count = " << mymap.bucket_count() << std::endl;
                      std::cout << "load_factor = " << mymap.load_factor() << std::endl;
                      std::cout << "max_load_factor = " << mymap.max_load_factor() << std::endl;

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{unordered_map::max_bucket_count}：返回容器拥有的最大bucket数量。
          \begin{cpp}
              // unordered_map limits
              #include <iostream>
              #include <unordered_map>

              int main ()
              {
                      std::unordered_map<int,int> mymap;

                      std::cout << "max_size = " << mymap.max_size() << std::endl;
                      std::cout << "max_bucket_count = " << mymap.max_bucket_count() << std::endl;
                      std::cout << "max_load_factor = " << mymap.max_load_factor() << std::endl;

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{unordered_map::max_load_factor}：返回或者设置容器的最大负载因子。
          \begin{cpp}
              // unordered_map::max_load_factor
              #include <iostream>
              #include <string>
              #include <unordered_map>

              int main ()
              {
              std::unordered_map<std::string,std::string> mymap = {
              {"Au","gold"},
              {"Ag","Silver"},
              {"Cu","Copper"},
              {"Pt","Platinum"}
              };

              std::cout << "current max_load_factor: " << mymap.max_load_factor() << std::endl;
              std::cout << "current size: " << mymap.size() << std::endl;
              std::cout << "current bucket_count: " << mymap.bucket_count() << std::endl;
              std::cout << "current load_factor: " << mymap.load_factor() << std::endl;

              float z = mymap.max_load_factor();
              mymap.max_load_factor ( z / 2.0 );
              std::cout << "[max_load_factor halved]" << std::endl;

              std::cout << "new max_load_factor: " << mymap.max_load_factor() << std::endl;
              std::cout << "new size: " << mymap.size() << std::endl;
              std::cout << "new bucket_count: " << mymap.bucket_count() << std::endl;
              std::cout << "new load_factor: " << mymap.load_factor() << std::endl;

              return 0;
              }
          \end{cpp}
    \item \cppinline{unordered_map::max_size}：返回容器的最大保存元素数量。
          \begin{cpp}
              // unordered_map limits
              #include <iostream>
              #include <unordered_map>

              int main ()
              {
                      std::unordered_map<int,int> mymap;

                      std::cout << "max_size = " << mymap.max_size() << std::endl;
                      std::cout << "max_bucket_count = " << mymap.max_bucket_count() << std::endl;
                      std::cout << "max_load_factor = " << mymap.max_load_factor() << std::endl;

                      return 0;
                  }
          \end{cpp}

    \item \cppinline{unordered_map::operator=}：重载重启赋值运算符，函数原型如下：
          \begin{cpp}
              unordered_map& operator= ( const unordered_map& ump );
              unordered_map& operator= ( unordered_map&& ump );
              initializer list
              unordered_map& operator= ( intitializer_list<value_type> il );
          \end{cpp}
          \begin{example}{无序map的赋值}


              \begin{cpp}
                  // assignment operator with unordered_map
                  #include <iostream>
                  #include <string>
                  #include <unordered_map>

                  typedef std::unordered_map<std::string,std::string> stringmap;

                  stringmap merge (stringmap a,stringmap b) {
                          stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
                      }

                  int main ()
                  {
                  stringmap first, second, third;
                  first = {{"AAPL","Apple"},{"MSFT","Microsoft"}};  // init list
                  second = {{"GOOG","Google"},{"ORCL","Oracle"}};   // init list
                  third = merge(first,second);                      // move
                  first = third;                                    // copy

                  std::cout << "first contains:";
                  for (auto& elem: first) std::cout << " " << elem.first << ":" << elem.second;
                  std::cout << std::endl;

                  return 0;
                  }
              \end{cpp}
          \end{example}
    \item \cppinline{unordered_map::operator[]}：重载运算符，获取key或者const key的元素。
          \begin{example}

              \begin{cpp}
                  // unordered_map::operator[]
                  #include <iostream>
                  #include <string>
                  #include <unordered_map>

                  int main ()
                  {
                          std::unordered_map<std::string,std::string> mymap;

                          mymap["Bakery"]="Barbara";  // new element inserted
                          mymap["Seafood"]="Lisa";    // new element inserted
                          mymap["Produce"]="John";    // new element inserted

                          std::string name = mymap["Bakery"];   // existing element accessed (read)
                          mymap["Seafood"] = name;              // existing element accessed (written)

                          mymap["Bakery"] = mymap["Produce"];   // existing elements accessed (read/written)

                          name = mymap["Deli"];      // non-existing element: new element "Deli" inserted!

                          mymap["Produce"] = mymap["Gifts"];    // new element "Gifts" inserted, "Produce" written

                          for (auto& x: mymap) {
                                  std::cout << x.first << ": " << x.second << std::endl;
                              }

                          return 0;
                      }
              \end{cpp}
          \end{example}
    \item \bashinline{unordered_map::rehash}：设置容器中的bucket数为n或者更大。
          \begin{cpp}
              // unordered_map::rehash
              #include <iostream>
              #include <string>
              #include <unordered_map>

              int main ()
              {
                      std::unordered_map<std::string,std::string> mymap;

                      mymap.rehash(20);

                      mymap["house"] = "maison";
                      mymap["apple"] = "pomme";
                      mymap["tree"] = "arbre";
                      mymap["book"] = "livre";
                      mymap["door"] = "porte";
                      mymap["grapefruit"] = "pamplemousse";

                      std::cout << "current bucket_count: " << mymap.bucket_count() << std::endl;

                      return 0;
                  }
          \end{cpp}
    \item \cppinline{unordered_map::reserve}：设置容器中的bucket数量为最合适接受n个bucket。
          \begin{example}
              \begin{cpp}
                  // unordered_map::reserve
                  #include <iostream>
                  #include <string>
                  #include <unordered_map>

                  int main ()
                  {
                          std::unordered_map<std::string,std::string> mymap;

                          mymap.reserve(6);

                          mymap["house"] = "maison";
                          mymap["apple"] = "pomme";
                          mymap["tree"] = "arbre";
                          mymap["book"] = "livre";
                          mymap["door"] = "porte";
                          mymap["grapefruit"] = "pamplemousse";

                          for (auto& x: mymap) {
                                  std::cout << x.first << ": " << x.second << std::endl;
                              }

                          return 0;
                      }
              \end{cpp}
          \end{example}
    \item \cppinline{unordered_map::size}：返回在容器中元素的的数目。
          \begin{example}
              \begin{cpp}
                  // unordered_map::size
                  #include <iostream>
                  #include <string>
                  #include <unordered_map>

                  int main ()
                  {
                  std::unordered_map<std::string,double> mymap = {
                  {"milk",2.30},
                  {"potatoes",1.90},
                  {"eggs",0.40}
                  };

                  std::cout << "mymap.size() is " << mymap.size() << std::endl;

                  return 0;
                  }
              \end{cpp}
          \end{example}
    \item \cppinline{unordered_map::swap}：交换容器中元素的内容，另一个容器中的元素的类型相同，大小不同。
          \begin{example}
              \begin{cpp}
                  // unordered_map::swap
                  #include <iostream>
                  #include <string>
                  #include <unordered_map>

                  int main ()
                  {
                  std::unordered_map<std::string,std::string>
                  first = {{"Star Wars","G. Lucas"},{"Alien","R. Scott"},{"Terminator","J. Cameron"}},
                  second  = {{"Inception","C. Nolan"},{"Donnie Darko","R. Kelly"}};

                  first.swap(second);

                  std::cout << "first: ";
                  for (auto& x: first) std::cout << x.first << " (" << x.second << "), ";
                  std::cout << std::endl;

                  std::cout << "second: ";
                  for (auto& x: second) std::cout << x.first << " (" << x.second << "), ";
                  std::cout << std::endl;

                  return 0;
                  }
              \end{cpp}
          \end{example}
\end{itemize}
\subsection{tuple}
\cppinline{std::tuple}是类似pair的模板。每个pair的成员类型都不相同，但每个pair都恰好有两个成员。不同\cppinline{std::tuple}类型的成员类型也不相同，但一个\cppinline{std::tuple}可以有任意数量的成员。每个确定的\cppinline{std::tuple}类型的成员数目是固定的，但一个\cppinline{std::tuple}类型的成员数目可以与另一个\cppinline{std::tuple}类型不同。

但我们希望将一些数据组合成单一对象，但又不想麻烦地定义一个新数据结构来表示这些数据时，\cppinline{std::tuple}是非常有用的。我们可以将\cppinline{std::tuple}看作一个”快速而随意”的数据结构。

当我们定义一个\cppinline{std::tuple}时，需要指出每个成员的类型。当我们创建一个\cppinline{std::tuple}对象时，可以使用tuple的默认构造函数，它会对每个成员进行值初始化；也可以为每个成员提供一个初始值，此时的构造函数是explicit的，因此必须使用直接初始化方法。类似make\_pair函数，标准库定义了make\_tuple函数，我们还可以使用它来生成\cppinline{std::tuple}对象。类似make\_pair，make\_tuple函数使用初始值的类型来推断tuple的类型。

一个\cppinline{std::tuple}类型的成员数目是没有限制的，因此，tuple的成员都是未命名的。要访问一个tuple的成员，就要使用一个名为get的标准库函数模板。为了使用get，我们必须指定一个显式模板实参，它指出我们想要访问第几个成员。我们传递给get一个tuple对象，它返回指定成员的引用。get尖括号中的值必须是一个整型常量表达式。与往常一样，我们从0开始计数，意味着get<0>是第一个成员。

为了使用tuple\_size或tuple\_element，我们需要知道一个tuple对象的类型。与往常一样，确定一个对象的类型的最简单方法就是使用decltype。

常见的成员函数：
\begin{itemize}
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/make_tuple.html}{make\_tuple}创建一个 tuple 对象，其类型根据各实参类型定义(函数模板)
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/tie.html}{tie} 创建左值引用的 tuple，或将 tuple 解包为独立对象(函数模板)
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/forward_as_tuple.html}{forward\_as\_tuple}创建转发引用的 tuple(函数模板)
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/tuple_cat.html}{tuple\_cat}通过连接任意数量的元组来创建一个tuple(函数模板)
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/get.html}{std::get(std::tuple)}元组式访问指定的元素(函数模板)
\item operator==、operator!=  (C++20 中移除)、operator<   (C++20 中移除)、operator<=  (C++20 中移除)、operator>   (C++20 中移除)、operator>=  (C++20 中移除)、operator<=> (C++20)      按字典顺序比较 tuple 中的值(函数模板)
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/swap2.html}{std::swap(std::tuple)}(C++11)特化 std::swap 算法(函数模板)
\end{itemize}
\textbf{辅助函数}
\begin{itemize}
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/tuple_size.html}{tuple\_size}在编译时获得 tuple 的大小(类模板特化)
\cppfile{sample/tuple_size_demo.cc}
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/tuple_element.html}{tuple\_element} 获得指定元素的类型(类模板特化)(C++11)特化 
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/uses_allocator.html}{std::uses\_allocator} 类型特征(类模板特化)
\item \href{https://www.apiref.com/cpp-zh/cpp/utility/tuple/ignore.html}{ignore} 用 tie 解包 tuple 时用来跳过元素的占位符(常量)
\cppfile{sample/tuple_apply_demo.cc}
\end{itemize}

\cppinline{std::tuple}的关系和相等运算符的行为类似容器的对应操作。这些运算符逐对比较左侧tuple和右侧tuple的成员。只有两个tuple具有相同数量的成员时，我们才可以比较它们。而且，为了使用tuple的相等或不等运算符，对每对成员使用==运算符必须都是合法的；为了使用关系运算符，对每对成员使用<必须都是合法的。由于tuple定义了<和==运算符，我们可以将tuple序列传递给算法，并且可以在无序容器中将tuple作为关键字类型。
\cppinline{std::tuple}的一个常见用途是从一个函数返回多个值。

\cppinline{std::tuple}是一个模板，允许我们将多个不同类型的成员捆绑成单一对象。每个tuple包含指定数量的成员，但对一个给定的tuple类型，标准库并未限制我们可以定义的成员数量上限。

\cppinline{std::tuple}中元素是被紧密地存储的(位于连续的内存区域)，而不是链式结构。\cppinline{std::tuple}：实现了多元组，这是一个编译期就确定大小的容器，可以容纳不同类型的元素。多元组类型在当前标准库中被定义为可以用任意数量参数初始化的类模板。每一模板参数确定多元组中一元素的类型。所以，多元组是一个多类型、大小固定的值的集合。
\cppfile{code/STL/tuple1/main.cpp}
\cppinline{std::forward_as_tuple()}：使用引用变量构造一个tuple对象。
\cppfile{code/STL/tuple2/main.cpp}

\cppinline{std::get()}：获取tuple指定元素的值。
\cppfile{code/STL/tuple5/main.cpp}

\cppinline{std::make_tuple()}：使用指定的参数构造一个合适的tuple。
\cppfile{code/STL/tuple4/main.cpp}

\cppinline{std::tie()}：使用参数的值构造一个tuple对象。
\cppfile{code/STL/tuple2/main.cpp}
\cppinline{std::tuple_cat()}：构造一个拼接的tuple。
\begin{cpp}
    // tuple_cat example
    #include <iostream>     // std::cout
    #include <utility>      // std::pair
    #include <string>       // std::string
    #include <tuple>        // std::tuple, std::tuple_cat, std::get

    int main ()
    {

            std::tuple<float,std::string> mytuple (3.14,"pi");
            std::pair<int,char> mypair (10,'a');

            auto myauto = std::tuple_cat ( mytuple, std::tuple<int,char>(mypair) );

            std::cout << "myauto contains: " << '\n';
            std::cout << std::get<0>(myauto) << '\n';
            std::cout << std::get<1>(myauto) << '\n';
            std::cout << std::get<2>(myauto) << '\n';
            std::cout << std::get<3>(myauto) << '\n';

            return 0;
        }
\end{cpp}
\subsubsection{C++ list}
list是一种序列式容器。list容器完成的功能实际上和数据结构中的双向链表是极其相似的，list中的数据元素是通过链表指针串连成逻辑意义上的线性表，也就是list也具有链表的主要优点，即：在链表的任一位置进行元素的插入、删除操作都是快速的。list的实现大概是这样的：list的每个节点有三个域：前驱元素指针域、数据域和后继元素指针域。前驱元素指针域保存了前驱元素的首地址；数据域则是本节点的数据；后继元素指针域则保存了后继元素的首地址。其实，list和循环链表也有相似的地方，即：头节点的前驱元素指针域保存的是链表中尾元素的首地址，list的尾节点的后继元素指针域则保存了头节点的首地址，这样，list实际上就构成了一个双向循环链。由于list元素节点并不要求在一段连续的内存中，显然在list中是不支持快速随机存取的，因此对于迭代器，只能通过“++”或“--”操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作，这点，是与vector等不同的地方。
\begin{itemize}
    \item \cppinline{list()}：声明一个空列表；
    \item \cppinline{list(n)}：声明一个有n个元素的列表，每个元素都是由其默认构造函数T()构造出来的
    \item \cppinline{list(n,val)}：声明一个由n个元素的列表，每个元素都是由其复制构造函数T(val)得来的
    \item \cppinline{list(n,val)}：声明一个和上面一样的列表
    \item \cppinline{list(first,last)}：声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素
    \item \cppinline{list(first,last)}：声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素
\end{itemize}
成员函数:
\begin{itemize}
    \item \cppinline{list.assign()}：给list赋值有两种使用方式:list.assign(n,val):将list中的元素替换为n个val。list.assign(list1.begin(),list1.end()):将list2中开始到结束的所有元素赋值给list
    \item \cppinline{list.back()}： 返回最后一个元素
    \item \cppinline{list.begin()}： 返回指向第一个元素的迭代器
    \item \cppinline{list.clear()}： 删除所有元素
    \item \cppinline{list.empty()}： 如果list是空的则返回true
    \item \cppinline{list.end()}： 返回末尾的迭代器,可以调用list容器的 end()： 函数来得到list末端下一位置，相当于：int a[n]中的第n+1个位置a[n]，实际上是不存在的，不能访问，经常作为循环结束判断结束条件使用。
    \item \cppinline{list.erase(iterator i)}：删除迭代器i引用的节点，返回一个迭代器，该迭代器指向被删除节点之后的元素。
    \item \cppinline{iterator erase(iterator first,iterator last)}：删除迭代器first和last所指范围内的节点并返回一个迭代器，该迭代器引用被删除节点之后的元素。
    \item \cppinline{list.front()}： 返回第一个元素
    \item \cppinline{list.get_allocator()}： 返回list的配置器
    \item \cppinline{list.insert()}： 插入一个元素到list中
    \item \cppinline{list.max_size()}： 返回list能容纳的最大元素数量
    \item \cppinline{list.merge()}： 合并两个list，合并两个链表并使之默认升序(也可改)，l1.merge(l2，greater<int>(); 调用结束后l2变为空，l1中元素包含原来l1 和 l2中的元素，并且排好序，升序。其实默认是升序，greater<int>()可以省略，另外greater<int>()是可以变的，也可以不按升序排列。
    \item \cppinline{list.pop_back()}： 删除最后一个元素
    \item \cppinline{list.pop_front()}： 删除第一个元素
    \item \cppinline{list.push_back()}： 在list的末尾添加一个元素
    \item \cppinline{list.push_front()}： 在list的头部添加一个元素
    \item \cppinline{list.rbegin()}： 返回指向第一个元素的逆向迭代器
    \item \cppinline{list.remove()}： 从list删除元素
    \item \cppinline{list.remove_if()}： 按指定条件删除元素
    \item \cppinline{list.rend()}： 指向list末尾的逆向迭代器
    \item \cppinline{list.resize()}： 改变list的大小
    \item \cppinline{list.reverse()}： 把list的元素倒转
    \item \cppinline{list.size()}： 返回list中的元素个数
    \item \cppinline{list.sort()}： 给list排序
    \item \cppinline{list.splice()}： 合并两个list。splice实现list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list：
          \begin{cpp}
              void splice ( iterator position, list<T,Allocator>& x  );  //

              void splice ( iterator position, list<T,Allocator>& x, iterator i  );

              void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last  );
          \end{cpp}
          将x的元素移动到目的list的指定位置，高效的将他们插入到目的list并从x中删除。目的list的大小会增加，增加的大小为插入元素的大小。x的大小相应的会减少同样的大小。前两个函数不会涉及到元素的创建或销毁。第三个函数会。指向被删除元素的迭代器会失效。position：目的list的位置，用来标明 插入位置x源list、first,last里需要被移动的元素的迭代器。区间为[first, last)。包含first指向的元素，不包含last指向的元素。]
    \item \cppinline{list.swap()}：交换两个list,一个是l1.swap(l2); 另外一个是swap(l1,l2)，都可能完成连个链表的交换
    \item \cppinline{list.unique()}：删除list中重复的元素
\end{itemize}
\cppfile{code/DS/ex6/main.cpp}
\subsection{\href{http://www.cplusplus.com/reference/map/map/}{std::map}}
\begin{itemize}
    \item \cppinline{at}：返回map容器在指定key处的值。
          \cppfile{code/STL/map21/main.cpp}
    \item \cppinline{map::begin}：返回指向map容器第一个元素的迭代器。
    \item \cppinline{map::cbegin}：返回指向map容器第一个元素的常量迭代器。
    \item \cppinline{map::cend}：返回指向map容器最后一个元素后的常量迭代器。
    \item \cppinline{map::clear}：删除map容器中的所有元素。删除后容器的size为0.
    \item \cppinline{map::count}：判断元素是否出现在容器中，结果为0或者1.
          \cppfile{code/STL/map15/main.cpp}
    \item \cppinline{map::crbegin}：返回指向容器最后一个元素的常量迭代器。
    \item \cppinline{map::crend}：返回指向容器第一个元素前一个元素的常量迭代器。
    \item \cppinline{map::emplace}：插入一个新的元素到maph容器。插入的元素为容器指定的类型。
          \cppfile{code/STL/map16/main.cpp}
    \item \cppinline{map::emplace_hint}：插入元素到map容器 ，函数返回插入元素后迭代器指向的位置。
          \cppfile{code/STL/map17/main.cpp}
    \item \cppinline{map::empty}：判断容器是否为空。
    \item \cppinline{map::end}：返回指向最后一个元素后的迭代器。
    \item \cppinline{map::equal_range}：返回小于等于给定key对应的元素和大于key对应的元素的元素。
          \cppfile{code/STL/map18/main.cpp}
    \item \cppinline{map::erase}：删除容器中的内容，可以删除迭代器指向的元素，或两个迭代器之间的元素或者key对应的元素。
          \cppfile{code/STL/map19/main.cpp}
    \item \cppinline{map::find}：返回指定元素的迭代器。如果元素不在容器中则返回map::end;
    \item \cppinline{map::get_allocator}：获取迭代器的分配器对象，可以通过此对象分配容器的大小和回收空间。
          \cppfile{code/STL/map20/main.cpp}
    \item \cppinline{map::insert}：插入元素到map中。可以通过迭代器指向的位置插入，或者根据pair插入。返回结果为一个指向插入的新的元素的迭代器和插入是否成功的pair。
          \cppfile{code/STL/map21/main.cpp}
    \item \cppinline{map::key_comp}：返回复制的比较对象。
          \cppfile{code/STL/map22/main.cpp}
    \item \cppinline{map::lower_bound}：返回指向小于等于指定元素的迭代器。
    \item \cppinline{map::max_size}：返回容器的最大大小。
    \item \cppinline{map::operator=}：使用当前map的元素给另一个元素里面的容器赋值。
    \item \cppinline{map::operator[]}：获取容器中指定key的值。
    \item \cppinline{map::rbegin}：获取指向容器最后一个元素的迭代器。
    \item \cppinline{map::rend}：获取指向容器第一个元素前一个元素额迭代器。
    \item \cppinline{map::size}：获取容器的大小。
    \item \cppinline{map::swap}：交换两个容器里面的内容。
          \cppfile{code/STL/map22/main.cpp}
    \item \cppinline{map::upper_bound}：获取大于指定元素的迭代器。
    \item \cppinline{map::value_comp}：返回可以用于比较两个元素值的比较对象。
          \cppfile{code/STL/map22/main.cpp}
\end{itemize}
